#include <iostream>
#include <list>
using namespace std;

/**
 * Created by huxin on 2017/9/13.
 *
 * 最长单调递增子序列问题
 * 
 *  F(x) //可以得出相应x的最长单调递增子序列
 *  Array_a{1, 3, 5, 2, 4, 6, 7, 8}
 *  1, 3, 4, 6, 7, 8
 *  1, 2, 4, 6, 7, 8
 *  1, 3, 5, 6, 7, 8
 *
 *  max{Array_a} = max{F(1), F(3), F(5), F(2), F(4), F(6), F(7), F(8)}
 *  {3, 5, 2, 4, 6, 7, 8} @1
 *  F(1) = max{F(@1)} = max{F(3), F(5), F(2), F(4), F(6), F(7), F(8)}
 *  result = max{F(a)}
 *  依赖关系式:
 *  a_n <= a_(n + 1)
 *  F(a_n) = max{F({a - a_n - a_(n - 1) -.....a_(n-1 == 0)}) + 1

 */
int MAX_ELEMENT_SUB_LENGTH[1000];

list<int> getArr(int *pArr, int nSize, int nPos){
    if(nPos == nSize)
        return {};
        
    list<int> nList;
    for(int i = nPos + 1; i < nSize; ++i){
        if(pArr[nPos] <= pArr[i]){
            nList.push_back(i);
        }
    }

    return nList; //返回比nPos元素大的索引
}

int getLength(int *pArr, int nSize, int nPos){
    if(nPos >= nSize - 1)
        return 0;
    if(MAX_ELEMENT_SUB_LENGTH[nPos] != -1)
        return MAX_ELEMENT_SUB_LENGTH[nPos];

    list<int> nIndexList = getArr(pArr, nSize, nPos);

    int nIndex = nPos, nMaxValue = -1;
    for(auto begin = nIndexList.begin(); begin != nIndexList.end(); ++begin){
        if(MAX_ELEMENT_SUB_LENGTH[*begin] == -1){
            int result = getLength(pArr, nSize, *begin);
            MAX_ELEMENT_SUB_LENGTH[*begin] = result;
        }

        if(nIndex == nPos){
            nIndex = *begin;
            nMaxValue = MAX_ELEMENT_SUB_LENGTH[*begin];
        }else if(MAX_ELEMENT_SUB_LENGTH[*begin] > nMaxValue){
            nIndex = *begin;
            nMaxValue = MAX_ELEMENT_SUB_LENGTH[*begin];
        }
    }
    int result = getLength(pArr, nSize, nIndex) + 1;
    // cout << result << endl;
    MAX_ELEMENT_SUB_LENGTH[nPos] = result;

    return result;
    // return 0;
}

int main(int argc, char *argv[])
{
    int arr[] = { 1, 3, 5, 2, 4, 6, 7, 8 };
    for(int i = 0; i < 1000; ++i){
        MAX_ELEMENT_SUB_LENGTH[i] = -1;
    }
    //创建树
    int nLen = sizeof(arr)/sizeof(int);
    for(int i = 0; i < nLen; ++i){
        int result = getLength(arr, nLen, i);
    }

    for(int i = 0; i < nLen; ++i){
        if(MAX_ELEMENT_SUB_LENGTH[i] != -1)
            cout << arr[i] << ": " << MAX_ELEMENT_SUB_LENGTH[i] << '\n';
    }
    cout << endl;
    return 0;
}